package bintree.leetcode;

import java.util.*;

public class 后继者 {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null){
            return null;
        }
        Deque<TreeNode>  stack = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (!stack.isEmpty()||cur!=null){
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            prev = cur ;
            if (prev==cur){
                return prev;
            }
            cur=cur.right;
    }
       return null;
    }
}
